사회를 연결하는 보이지 않는 실을 수학적으로 어떻게 설명할 수 있을까요? 예를 들어, 벨라 루고시와 할리우드 아이콘들을 연결하는 베이컨 번호 베이컨 번호로 벨라 루고시를 할리우드 아이콘들과 연결하거나, 유사성 그래프 근접도에 따라 데이터 포인트를 군집화하는, 그래프 이론 은 이러한 이산 세계를 모델링하기 위한 공식적인 언어 $G = (V, E)$를 제공합니다.
1. 그래프의 구조
핵심적으로, 그래프는 집합 정점 ($V$)와 집합 간선 ($E$)으로 구성됩니다. 그러나 규칙은 구조에 따라 달라집니다:
- 단순 그래프: 가장 우아한 형태이며, 다음을 금지합니다: 루프(정점에서 자신에게 연결되는 간선) (정점이 자기 자신과 연결되는 간선)과 병렬 간선(같은 두 정점 사이의 중복된 간선) (같은 두 점 사이의 중복된 간선).
- 다중 그래프: 루프와 병렬 간선을 허용하며, 같은 두 노드 사이의 다양한 상호작용(예: 문자 메시지와 통화)을 모델링하는 데 자주 사용됩니다.
- 고립 정점: 정점 $v$가 자신과 연결된 간선이 없을 경우, 고립 정점이라 하며, 현재 집합 내에서 관계가 없는 객체를 나타냅니다.
근접성의 논리
데이터 과학에서는 종종 비유사도 함수 를 사용하여 그래프를 생성합니다:
$$s(v, w) = |p_1 - q_1| + |p_2 - q_2| + |p_3 - q_3|$$
특정 임계값보다 $s(v, w)$ 값이 낮을 때만 $v$와 $w$ 사이에 간선을 그립니다. 이는 '이웃' 네트워크를 효과적으로 구축하는 것입니다.
2. 경로, 연결성 및 컴포넌트
경로 는 정점과 간선의 순서입니다. 만약 경로가 어떤 정점을 한 번 이상 방문하지 않는다면, 이를 단순 경로라고 합니다. 연결성은 그래프의 심장입니다: 단순 경로. 연결성은 그래프의 심장입니다:
- 연결 그래프: 그래프 내 모든 정점 쌍 사이에 경로가 존재합니다. 모든 정점 쌍 사이에 경로가 존재합니다.
- 컴포넌트: 그래프가 연결되어 있지 않으면, 서로 겹치지 않는 조각들로 나뉘며, 이를 컴포넌트라고 합니다. 각 컴포넌트는 최대 연결 부분 그래프입니다.
3. 부분 그래프: 부분집합의 구조
부분 그래프 $G' = (V', E')$는 $V'$의 모든 정점이 $V$에 포함되며, $E'$의 모든 간선이 $V'$에 있는 정점들을 연결하는 그래프 $G$의 부분집합입니다. 부분 그래프를 식별하는 것은 전반적인 네트워크 내에서 국지적인 패턴을 탐지하는 데 필수적입니다.
🎯 핵심 원리: 손 맞잡기 법칙
임의의 무방향 그래프에서 모든 정점의 차수의 합은 간선 수의 두 배입니다. 이는 홀수 차수를 가진 정점의 개수가 반드시 짝수여야 함을 의미합니다.
$$\sum_{v \in V} \text{deg}(v) = 2|E|$$